package leetCode.solution;

/**
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
import java.util.Deque;
import java.util.LinkedList;

import com.alibaba.fastjson.JSON;

public class Solution42 {
	public int trap1(int[] height) {
		int n = height.length;
		if(height==null || n==0) return 0;
		
		int lMax = 0;
		int leftMax[] = new int[n];
		for(int i=0;i<n;i++) {
			lMax = Math.max(lMax, height[i]);
			leftMax[i] = lMax;
		}
		
		int rMax = 0;
		int rightMax[] = new int[n];
		for(int i=n-1;i>=0;i--) {
			rMax = Math.max(rMax, height[i]);
			rightMax[i] = rMax;
		}
		int sum = 0;
		for(int i =0;i<n;i++) {
			sum+=Math.min(leftMax[i], rightMax[i])-height[i];
		}
		return sum;
	}
	public int trap3(int[] height) {
		int n = height.length;
		if(height==null || n==0) return 0;
		
		int lMax = 0;
		int rMax = 0;
		int rightMax[] = new int[n];
		for(int i=n-1;i>=0;i--) {
			rMax = Math.max(rMax, height[i]);
			rightMax[i] = rMax;
		}
		int sum = 0;
		for(int i =0;i<n;i++) {
			lMax = Math.max(lMax, height[i]);
			sum+=Math.min(lMax, rightMax[i])-height[i];
		}
		return sum;
	}
	
	public int trap2(int[] height) {
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = height.length;
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stack.push(i);
        }
        return ans;
    }
	
	// 左右指针
	public int trap4(int[] height) {
		int n = height.length;
		if(height==null || n==0) return 0;
		
		int lMax = height[0];
		int rMax = height[n-1];
		int sum = 0;
		for(int i=1,j=n-2;i<=j;) {
			if(lMax<=rMax) {
				lMax=Math.max(lMax, height[i]);
				sum+=lMax-height[i++];
			}else if(lMax>rMax) {
				rMax=Math.max(rMax, height[j]);
				sum+=rMax-height[j--];
			}
		}
		
		return sum;
	}
	
	public static void main(String[] args) {
		int maxNum = 20;
		int maxSize = 5;
		for(int i =0;i<500000;i++) {
			int size = (int)(Math.random()*maxSize);
			int []arr = new int[size];
//			int []arr = new int[] {6,11,10,11};
			for(int j=0;j<size;j++) {
				arr[j] = (int)(Math.random()*maxNum);
			}
			int result1 = new Solution42().trap1(arr);
			int result2 = new Solution42().trap2(arr);
			int result3 = new Solution42().trap3(arr);
			int result4 = new Solution42().trap4(arr);
			if(result1!=result2 || result1!=result3 || result1!=result4) {
				System.out.println(result1);
				System.out.println(result2);
				System.out.println(result3);
				System.out.println(result4);
				System.out.println(JSON.toJSONString(arr));
				break;
			}
			
		}
		
	}

}